package arithmetic.leetcode;

/**
 * @author zhangzg
 * @date 2023/4/19
 * 排序归来
 */
public class Sort {


    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] nums){
        if(nums.length == 0){
            return;
        }
        for (int i =0; i<nums.length; i++){
            for (int j =0; j<nums.length-1-i; j++){
                if(nums[j] > nums[j+1]){
                    int temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
    }

    /**
     * 选择排序:可以看成是冒泡排序的优化
     *  不断的选择剩余元素之中的最大或者最小
     */
    public static void choiceSort(int[] nums){
        if (nums.length == 0) {
            return;
        }
        for (int i =0; i<nums.length; i++){
            int minIndex = i;//最小数的下标，每次循环开始总是假设第一个数最小
            for (int j = i; j<nums.length; j++){
                if(nums[minIndex] > nums[j]){
                    minIndex = j;//将最小数的索引保存
                }
            }
            int temp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = temp;
        }
    }

    /**
     * 插入排序
     * 在已排好序中从后向前扫描，找到相应位置并插入
     * 升序
     */
    public static void insertSort(int[] nums){

        if (nums.length == 0){
            return;
        }
        int currValue;//当前待排序数据，该元素之前的元素均已被排序过
        for (int i=0; i<nums.length-1; i++){
            int preIndex = i;//已被排序数据的索引
            currValue = nums[preIndex+1];
            while (preIndex >= 0 && nums[preIndex] > currValue){
                nums[preIndex+1] = nums[preIndex];
                preIndex--;
            }
            nums[preIndex + 1] = currValue;//while循环结束说明已经找到待排序数据的合适位置，插入。
        }
    }

    /**
     * 快速排序
     * 1、首先任意选取一个数据作为关键数据，我们称为基准数。然后将所有比它小的数都放到它前面，所有比他大的数都放到它后面。
     * 2、通过一趟快速排序将要排序的数据分隔成独立的两部分。整个排序过程可以递归进行。
     *
     * 基准数:一般就是取要排序列的第一个
     *
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     *
     */
    public static void qSort(int[] nums, int left, int right){

        int base = nums[left];//选取我们的基准数
        int ll = left; //从左边找的位置
        int rr = right;//从右边找的位置
        while (ll < rr){
            //从后面往前找比基准数小的数
            while (ll < rr && nums[rr] >= base){
                rr--;
            }
            if(ll < rr){
                //找到了比基准数大的
                int temp = nums[rr];
                nums[rr] = nums[ll];
                nums[ll] = temp;
                ll++;
            }
            while (ll < rr && nums[ll] <= base){
                ll++;
            }
            if(ll < rr){
                //找到了比基准数大的
                int temp = nums[rr];
                nums[rr] = nums[ll];
                nums[ll] = temp;
                rr--;
            }
            //分成三部分
            qSort(nums, left,ll-1);
            qSort(nums,ll+1, right);
        }
    }

    /**
     * 堆排序
     * 应用: TOPK问题,用堆排序
     * 1、优先队列
     * 2、给你一个包含一亿关键词的用户检索的日志，如何获取排行榜前10的关键词
     */
    public static void heapSort(int[] nums){
        int len = nums.length;
        for (int i = len/2 -1; i>=0; i--){
            maxHeap(nums,i,len);//构建堆
        }
        for (int i = len - 1; i>0; i--){
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            maxHeap(nums,0,i);
        }
    }

    //创建一个大顶堆
    public static void maxHeap(int[] nums, int start, int end) {
        int parent = start;
        int son = parent * 2 +1;//下标从零开始就要加1，从1就不用
        while (son < end){
            int temp = son;
            if(son + 1 < end && nums[son] < nums[son + 1]){ //标识右节点比左节点大
                temp = son + 1; //换右节点跟父节点比较
            }
            if(nums[parent] > nums[temp]){
                return;
            }else {
                int i = nums[parent];
                nums[parent] = nums[temp];
                nums[temp] = i;
                parent = temp;//继续堆化
                son = parent*2 + 1;
            }
        }
        return;
    }

    /**
     * 归并排序：对于给定一组数据,利用递归与分治技术将数据序列划分为越来越小的半子表，
     *          在对半子表排序后，再用递归方法将排好序的半子表合并成为越来越大的有序序列。
     */
    public static void mergeSort(int[] nums, int left, int right){
        if(left < right){ //相等了就表示只有一个数了，不用继续拆分了
            int mid = (left + right)/2;
            mergeSort(nums,left,mid);
            mergeSort(nums,mid+1,right);
            //分完了接下来就要进行合并，也就是归的过程
            meger(nums, left, mid, right);
        }
    }
    public static void meger(int[] nums, int left, int mid, int right) {
        int[] temp = new int[nums.length];//借助一个临时数组用来保存合并的数据
        int point1 = left;//表示左边的第一个数的位置
        int point2 = mid + 1;//标识右边的第一个数的位置
        int loc = left;//表示我们当前以及到了那个位置
        while (point1 <= mid && point2 <= right){
            if(nums[point1] < nums[point2]){
                temp[loc] = nums[point1];
                point1++;
                loc++;
            }else {
                temp[loc] = nums[point2];
                point2++;
                loc++;
            }
        }
        //左边的数组还有剩余的
        while (point1 <= mid){
            temp[loc++] = nums[point1++];
        }
        //右边的数组也有剩余的
        while (point2 <= right){
            temp[loc++] = nums[point2++];
        }
        //把temp数组的元素复制到nums中
        for (int i = left; i <= right; i++){
            nums[i] = temp[i];
        }

    }

}


